//
// Created by gushen610140 on 2024/5/23.
//

#ifndef DATASTRUCTURECOURSE_GBINARAYSEARCHTREE_H
#define DATASTRUCTURECOURSE_GBINARAYSEARCHTREE_H

#include <vector>
#include <iostream>

class Node {
public:
    int value;
    Node *left;
    Node *right;

    explicit Node(int value) : value(value), left(nullptr), right(nullptr) {}
};

class GBinaraySearchTree {
private:
    Node *_root;
    int _count;
public:

    bool search(Node *current, int value, Node *parent, Node *&finder) {
        if (!current) {
            finder = parent;
            return false;
        }
        if (value > current->value) {
            return search(current->right, value, current, finder);
        } else if (value < current->value) {
            return search(current->left, value, current, finder);
        } else {
            finder = current;
            return true;
        }
    }

    void create(std::vector<int> list) {
        for (const int &item: list) {
            Node *finder;
            if (!search(_root, item, nullptr, finder)) {
                _count++;
                if (!finder) {
                    finder = new Node(item);
                    _root = finder;
                } else {
                    Node *newNode = new Node(item);
                    if (item < finder->value) {
                        finder->left = newNode;
                    } else {
                        finder->right = newNode;
                    }
                }
            }
        }
    }

    Node *&findBiggest(Node *&node) {
        if (node->right) {
            return findBiggest(node->right);
        }
        return node;
    }

    void remove(Node *&current) {
        if (!current->right) {
            current = current->left;
        } else if (!current->left) {
            current = current->right;
        } else {
            std::swap(current->value, findBiggest(current->left)->value);
            remove(findBiggest(current->left));
        }
    }

    void remove(Node *&current, int value) {
        if (!current) {
            throw std::out_of_range("Not Find");
        }
        if (value > current->value) {
            remove(current->right, value);
        } else if (value < current->value) {
            remove(current->left, value);
        } else {
            remove(current);
        }
    }

    void preorder(Node *node) {
        if (!node) {
            return;
        }
        std::cout << node->value << ' ';
        preorder(node->left);
        preorder(node->right);
    }

    void inorder(Node *node) {
        if (!node) {
            return;
        }
        inorder(node->left);
        std::cout << node->value << ' ';
        inorder(node->right);
    }

    Node *&getRoot() {
        return _root;
    }

    int getCount() {
        return _count;
    }

    GBinaraySearchTree() : _root(nullptr), _count(0) {}

};


#endif //DATASTRUCTURECOURSE_GBINARAYSEARCHTREE_H
